/*
 * com.future CO.,ltd.
 */

package com.future;

import com.future.util.TreeNode;

import java.util.*;

/**
 * Description: 99. 恢复二叉搜索树
 * 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
 *
 * @Author: future
 * @Date:2022/5/2:22:31
 */
public class Solution_99_recoverTree {

    public static void main(String[] args) {
        TreeNode head = new TreeNode(25);
        // head.val = 10;
        head.left = new TreeNode(5);
        head.right = new TreeNode(20);
        head.left.left = new TreeNode(2);
        head.left.right = new TreeNode(8);
        head.right.left = new TreeNode(15);
        // head.right.right = new TreeNode(25);
        head.right.right = new TreeNode(10);
        recoverTree(head);
    }

    /**
     * 二叉搜索树的中序遍历就是递增数组
     * 1、先用中序遍历放到一个数组
     * 2、找到第一个违反顺序结构的数firstLarge
     * 3、找到比firstLarge小的最后一个数lastLess
     * 4、递归遍历二叉搜索树，把对应节点跟firstLarge和lastLess互换
     * done
     *
     * @param root
     */
    public static void recoverTree(TreeNode root) {
        if (root == null) {
            return;
        }
        List<Integer> inOrder = new ArrayList<>();
        process(inOrder, root);
        boolean start = false;
        int firstLarge = Integer.MIN_VALUE;
        int lastLess = Integer.MIN_VALUE;
        for (int i = 1; i < inOrder.size(); i++) {
            if (inOrder.get(i - 1) > inOrder.get(i) && !start) {
                firstLarge = inOrder.get(i - 1);
                lastLess = inOrder.get(i);
                start = true;
            } else if (firstLarge > inOrder.get(i) && start) {
                lastLess = inOrder.get(i);
            } else if (start) {
                break;
            }
        }
        changeValue(root, firstLarge, lastLess, false, false);
        inOrder.clear();
        process(inOrder, root);
        for (Integer s : inOrder) {
            System.out.print(s + " ");
        }
    }

    /**
     * @param root
     * @param firstLarge
     * @param preVal
     * @param modify1    标记firstLarge已经被修改
     * @param modify2    标记preVla已经被修改
     */
    private static void changeValue(TreeNode root, int firstLarge, int preVal, Boolean modify1, Boolean modify2) {
        if (root == null || modify1 && modify2) {
            return;
        }
        if (root.val == firstLarge && !modify1) {
            root.val = preVal;
            modify1 = true;
        } else if (root.val == preVal && !modify2) {
            root.val = firstLarge;
            modify2 = true;
        }
        changeValue(root.left, firstLarge, preVal, modify1, modify2);
        changeValue(root.right, firstLarge, preVal, modify1, modify2);
    }


    private static void process(List<Integer> inOrder, TreeNode root) {
        if (root == null) {
            return;
        }
        process(inOrder, root.left);
        inOrder.add(root.val);
        process(inOrder, root.right);
    }
}
